1. Field of the Invention
The present invention relates to a communication control system based on the Asynchronous Transfer Mode in the Broadband aspects of ISDN (called B-ISDN for short hereinbelow). In particular, it relates to an improvement of the performance of the asynchronous transfer by providing control means for controlling the asynchronous data transfer via each of a plurality of virtual circuits.
2. Description of the Prior Art
In the Asynchronous Transfer Mode, a frame prepared as a minimum data unit of information to be transferred is divided into a plurality of cells having a fixed bit length. The effective transfer rates via the respective virtual circuit can be adjusted by controlling the intervals between transfers of cells in accordance with the asynchronous transfer.
This control technique is called the average rate control. The average rate control is implemented by the leaky bucket algorithm. One example will be explained in the followings.
An exemplary prior art communication control system comprises a cell transfer unit 2 and a controller 1 for controlling the transfer of cells on the basis of of the leaky bucket algorithm as illustrated in FIG. 1. The controller 1 includes the following three elements, i.e., a virtual circuit control unit 101, a rate control unit 102 and a transfer determination unit 103.
The virtual circuit control unit 101 is used to control virtual circuits through which cells are desired to be transferred. The rate control unit 102 is used to perform calculation on the basis of the leaky bucket algorithm as described herein and output the result thereof. The transfer determination unit 103 is used to determine which of the virtual circuits is next permitted to transfer a cell in accordance with the result of the calculation and to inform the cell transfer unit 2 of the virtual circuit thus determined.
The leaky bucket algorithm will be explained hereinbelow with reference to the diagram illustrating the variation of the credit which decreases with time after the transmission of a cell as illustrated in FIG. 2.
In accordance with the leaky bucket algorithm, a predetermined credit P is added to the current credit W at each transmission. The updated credit W is then decreased in proportion to the time passing thereafter by subtracting a predetermined credit dW per unit time. When the credit W is smaller than a certain threshold value T, the transmission of a cell is permitted.
In the case as illustrated in FIG. 2, the transmission of a cell is not permitted in the time periods A but permitted in the time periods B.
Two methods have been employed in the prior art techniques. The two methods will be explained hereinbelow also with reference to FIG. 3.
In accordance with one method, the credits W corresponding to the respective virtual circuits are decreased as the time passes. Each credit W is compared with the threshold value T at each time point in order to determine whether or not it is permitted to transfer a cell through each corresponding virtual circuit.
In accordance with the other method, the following equation is calculated at the time point tn in order to obtain the time point tCn+1 at which the subsequent cell can be transferred. The next cell to be transferred is determined by comparing the time point tCn+1 of each virtual circuit to the present time. EQU Wn=P+Wn-1-(tn-tn-1).times.dW EQU tCn+1=tn+(Wn-T)/dW(Wn&gt;T) EQU tCn+1=tn+1(Wn.ltoreq.T) (1)
where tn is the time point at which the n-th cell is transferred through the virtual circuit in question; Wn is the credit which is increased by a certain value P when the n-th cell is transferred; and dW is a decrement per unit time. If a minimum interval C between adjacent transmissions is introduced, the following equation is employed instead of the above equation (1). EQU tCn+1=tn+C(dTn.ltoreq.C) EQU tCn+1=tn+dTn (dTn&gt;C) (2) EQU where EQU dTn=(Wn-T)/dw(Wn&gt;T) EQU dTn=0((Wn.ltoreq.T) (3)
Since the unit time dW is usually 1, the above equations (1) and (2) are rearranged as follows and implemented by 0 judgement means and addition/subtraction means. EQU Wn=P+Wn-1-(tn-tn-1) EQU tCn+1=tn+@(@(Wn-T)-C)+C (4) EQU where EQU @(x)=0 (x.ltoreq.0) EQU @(x)=x (x&gt;0)
Namely, in accordance with the second method, the time point tCn+1 at which the subsequent cell can be transferred is calculated at the transmission time of the preceding cell by means of the virtual circuit control unit 101 and thereafter compared with the present time by means of the transfer determination unit 103 in order to determine the next cell to be transferred. The result of determination is given to the cell transfer unit 2.
As described above, there are several shortcomings as follows in the case of the first method and the second method of the conventional communication control systems.
The virtual circuit control unit 101 shown in FIG. 1 is usually provided with means for storing the results of calculation for rate control by the rate control unit 102 as credits indicative of the rate control information. The rate control information corresponding to one virtual circuit is read from the virtual circuit control unit 101 by the rate control unit 102.and subjected to arithmetic logical operation with the time information stored in the rate control unit 102, followed by writing the result of the arithmetic logical operation back to the storing means in the virtual circuit control unit 101.
In the case that each line of k virtual circuits is given a private credit W(m) (m=1,2,3, . . . k) respectively in accordance with the first method, k credits must be stored in the storing means in the virtual circuit control unit 101, read out to subtract the unit time dW therefrom and written back to the storing means in the virtual circuit control unit 101.
Because of this, when the number k of virtual circuits is increased, it becomes difficult to perform the reading, the subtraction and the writing back of the respective credits within an predetermined available time.
In accordance with the second method, since the reading operation, the calculation and the writing back of the credit W is carried out only with respect to the virtual circuit via which transmission of a cell is instantly determined by the transfer determination unit 103, the task of the rate control unit 102 is not increased in proportion to the number k of virtual circuits so that the above described problem no longer arises.
However, in the case that there is a request for transferring a cell at the time point tn+1 when substantial time passes after the time point tCn+1 at which the transmission of a cell becomes possible as illustrated in FIG. 3, i.e., in the case that there is no cell to be transferred for a relatively long time after transmission of a preceding cell, the following problem arises.
The logical operation necessary for determining the respective time point and the judgement of the transmission of a cell are implemented by carrying out logical operation and the comparison between the counted number in a present time counter indicative of the present time and the respective number corresponding to the time point necessary is for controlling the transmission rate stored in the virtual circuit control unit 101. The present time counter is commonly utilized for all the virtual circuits since it is difficult to provide a respective private counter for each virtual circuit when the number of virtual circuits is large.
In the case of the second method, the transfer determination unit 103 makes determination of whether or not a cell can be transferred with respect to the registered virtual circuits in turn. Namely, the determination is made by comparing the present time tn+1 counted in the present time counter to the transfer enabling time tCn+1 stored in memory means of the virtual circuit control unit 101 and indicative of the time point at which transmission of a next cell becomes possible. However, since the present time counter has a finite number of available bits and always carries out counting up, the present time counter possibly overflows, resulting in the negative difference in the counted number between the transfer enabling time tCn+1 and the present time tn+1. The transfer determination unit 103 therefore erroneously judges that it is not yet permitted to transfer a cell because of the negative difference.
This problem will be explained in details in the case that the judgement is made based upon the most significant bit of the sum of the number A counted by a 18 bit present time counter indicative of the present time and the complement B' of the number B indicative of the transfer enabling time. In this case, if the most significant bit of the sum is 0 the difference A-B is positive while if the most significant bit of the sum is 1 the difference A-B is negative.
There arise in this case a problem, for example, when a cell is transferred at time FF00H (the last H is simply indicative of the hexadecimal number) followed by storing the next transfer enabling time 0100H (after the overflow across FFFFH and 0000H). Namely, the judgement in the transfer determination unit 108 is made on the basis of the difference calculated by subtracting the transfer enabling time from the present time. When the present time lies between FF01H and 00FFH, it is correctly judged that the transmission is permitted because the difference is negative. However, when the present time lies between 8100H and 0100H, it is erroneously Judged that the transmission is not permitted because the difference is positive.
This will be easily understood from FIG. 4 showing a clock-like diagram. Namely, the difference A-B indicates the transfer enabling time B as the future or the past, irrespective of the actual time passing, in accordance with in which side the transfer enabling time B is located as seen from the midpoint (8100) corresponding to 180 degrees with the entire span being 380 degrees. When the present time passes the midpoint (8100), the transfer enabling time B is recognized not to be reached.
Furthermore, it is also the case that the difference between the preceding transmission time tn and the subsequent transmission time tn+1 can not correctly be calculated in the same manner as the difference A-B in the following equation for calculating the credit. EQU Wn+1=P+Wn-(tn+1-tn)